package zuochengyun;

//邮局选址问题
public class PoseOfficeAddressProblem {
	
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 100};
		PoseOfficeAddressProblem object = new PoseOfficeAddressProblem();
		System.out.println(object.minDistance(arr, 2));
	}

	//一维情况下，arr代表居民的地址坐标，num表示可以建的邮局的个数
	public int minDistance(int[] arr, int num){
		if(arr == null || arr.length <= 0 || num < 1 || arr.length < num){
			return 0;
		}
		//w[i][j]表示在arr[i...j]中只建一个邮局时，最短的总距离为多少
		//当只建一个邮局时，建在中点显然是最短的，对于偶数而言选哪个中点则都是一样的
		
		//注意这里w的长度是arr.length + 1
		int[][] w = new int[arr.length + 1][arr.length + 1];
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				//可以通过arr[i...j - 1]求出arr[i...j]
				w[i][j] = w[i][j - 1] + arr[j] - arr[(i + j) / 2];
			}
		}
		
		for (int i = 0; i < w.length; i++) {
			for (int j = 0; j < w[0].length; j++) {
				System.out.print(w[i][j] + "  ");
			}
			System.out.println();
		}
		
		//dp[i][j]表示在arr[0...j]上建立i + 1 个邮局最短距离
		int[][] dp = new int[num][arr.length];
		for (int j = 0; j < dp[0].length; j++) {
			dp[0][j] = w[0][j];		//当只建一个邮局时，就等于w数组
		}
		//当arr[0...j]建不止一个邮局时
		//比如arr[-3, -2, -1, 0, 1, 2], 要计算dp[2][5]的值
		//方案1：邮局1,2 负责-3这个点，邮局3负责[-2, -1, 0, 1, 2]
		//方案2：邮局1,2 负责-3, -2这个点，邮局3负责[-1, 0, 1, 2]
		//......
		//方案n：邮局1,2 负责-3, -2, -1, 0, 1, 2这个点，邮局3负责[]
		//所以dp[i][j] = min{dp[i - 1][k] + w[k + 1][j](0 =< k < j)}
		for (int i = 1; i < dp.length; i++) {
			for (int j = i + 1; j < dp[0].length; j++) {
				dp[i][j] = Integer.MAX_VALUE;
				for (int k = 0; k < j; k++) {
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + w[k + 1][j]);
				}
			}
		}
		
		System.out.println("-----");
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				System.out.print(dp[i][j] + "     ");
			}
			System.out.println();
		}
		return dp[num - 1][arr.length - 1];
	}
}
